import numpy as np


class Page:
    def __init__(self, num, time):
        # 记录页面号
        self.num = num
        # 记录调入内存时间
        self.time = time


class Pra:
    # 初始化内存单元，缓冲区
    def __init__(self, way, M, N, a):
        # 以上设定了默认值
        self.queue = []  # 记录调入队列
        self.block_list = []  # 记录当前哪块物理块出事了
        self.if_lack = []  # 记录是否缺页，1代表lack，0代表不lack
        self.k = -1  # 每载入一次加一 即缺页次数
        self.flag = -1  # 标记内存4个空
        self.a = list(a)  # 需要排序的页面列表
        self.M = int(M)  # 缓冲区的大小
        self.N = int(N)  # 需要排序的页面列表的长度
        # 初始化内存单元
        self.b = [Page(-1, self.M-i-1) for i in range(0, self.M)]
        # 初始化内存当前状态，缓冲区 初始化页号全为-1
        self.c = [[-1 for i in range(0, self.N)] for j in range(0, self.M)]
        self.way = way
        self.fifo_use = [0 for i in range(self.M)]

    # 取得在内存中停留最久的页面，默认状态下为最早点入的页面
    def get_max(self, b):
        max = -1
        flag = 0
        for i in range(0, self.M):
            if b[i].time > max:
                max = b[i].time
                flag = i
        return flag

    # 判断页面是否已在内存中（fold为需要判断的页面）
    def equation(self, fold, b):
        for i in range(0, self.M):
            if fold == b[i].num:
                return i  # 返回页面序号
        return -1

    # FIFO 算法
    def fifo(self, fold):
        val = self.equation(fold, self.b)
        if val >= 0:
            self.if_lack.append(0)
            self.block_list.append(val)
            pass  # 如果要调入的页内存中已存在则跳过
        else:
            self.if_lack.append(1)
            self.queue.append(fold)
            self.k += 1  # 缺页数加一
            if self.flag < self.M-1:
                self.flag += 1
                val = self.flag
                for i in range(self.flag):
                    self.fifo_use[i] += 1

            else:  # index_max = fifo_use.index(max(fifo_use))
                index_max = self.fifo_use.index(max(self.fifo_use))
                val = index_max
                self.fifo_use = [i + 1 for i in self.fifo_use]
                self.fifo_use[val] = 1
            self.b[val].num = fold
            self.block_list.append(val)


    # LRU 算法
    def lru(self, fold):
        val = self.equation(fold, self.b)
        if val >= 0:
            self.if_lack.append(0)
            self.block_list.append(val)
            self.b[val].time = 0 # 如果已经存在则刷该页面新时间
            for i in range(0, self.M):
                if i != val: # 其余页面时间加一
                    self.b[i].time += 1
        else:
            self.if_lack.append(1)
            self.queue.append(fold)
            self.k += 1 # 新页调入就得加一
            val = self.get_max(self.b) # 找到最旧的页面
            self.block_list.append(val)
            self.b[val].num = fold # 替换该页面
            self.b[val].time = 0
            for i in range(0, self.M):
                if i != val:  # 其余页面时间加一
                    self.b[i].time += 1

    # OPT 算法
    def opt(self, fold, index):
        # index记录当前页序号
        maxx = -1
        val = self.equation(fold, self.b)
        if val >= 0:
            self.if_lack.append(0)
            self.block_list.append(val)
            pass
        else:
            self.if_lack.append(1)
            self.queue.append(fold)
            self.k += 1

            for i in range(0, self.M):
                for j in range(index+1, self.N):
                    if self.b[i].num==self.a[j]:
                        # 这里的时间指的是距离下次使用的时间
                        self.b[i].time = j-i
                        break
                    else: # 不会再用到的设置非常大的时间
                        self.b[i].time = 999

            for i in range(0, self.M):
                if self.b[i].num == -1: # 如果有空位
                    val = i
                    break
                else:
                    if self.b[i].time > maxx: # 找到缓冲区时间最长的
                        maxx = self.b[i].time
                        val = i
            self.block_list.append(val)
            self.b[val].num = fold

    def reset(self):  # 重置内存区、队列等，便于更换算法
        self.b = [Page(-1, self.M - i - 1) for i in range(0, self.M)]
        self.c = [[-1 for i in range(0, self.N)] for j in range(0, self.M)]
        self.queue = []
        self.k = -1

    # 打印内存状态
    def print_out(self):
        return self.k + 1, round(float(self.k + 1) / self.N, 4), self.if_lack, self.block_list, self.queue

    # 主程序
    def process(self):
        # fifo算法
        print('come')
        if self.way == "FIFO":
            # print("ok,fifo")
            self.reset()
            for i in range(0, self.N):  # 逐个存入
                self.fifo(self.a[i])
                # 记录当前的内存单元中的页面（即一列）
                for j in range(0, self.M):
                    self.c[j][i] = self.b[j].num
            # print("fifo算法内存状态为：")
            return self.print_out()

        # lru算法
        elif self.way == "LRU":
            print('ok')
            self.reset()
            for i in range(0, self.N):
                self.lru(self.a[i])
                # 记录当前的内存单元中的页面
                for j in range(0, self.M):
                    self.c[j][i] = self.b[j].num
            # print("lru算法内存状态为：")
            return self.print_out()

        # opt 算法
        elif self.way == "OPT":
            self.reset()
            for i in range(0, self.N):
                self.opt(self.a[i], i)
                # 记录当前的内存单元中的页面
                for j in range(0, self.M):
                    self.c[j][i] = self.b[j].num
            # print("opt算法内存状态为：")
            return self.print_out()
        else:
            # print(type(self.way))
            return -1, -1


def del_adjacent(iterable):
    prev = object()
    for iter_m in iterable:
        if iter_m != prev:
            prev = iter_m
            yield iter_m


def duplicate_removal(iterable):
    a = del_adjacent(iterable)
    return list(a)


def cacu_res(way, physical_block, page_queen_len, page_cf_num, random_a):
    p = Pra(way, physical_block, page_queen_len, random_a)
    _, page_fault_rate, if_lack, block_list, in_list = p.process()
    print(page_fault_rate)
    return page_fault_rate, if_lack, block_list, in_list

